package top.swimmer.tokenizer.dictionary.trie;

import java.util.*;

/**
 * Created by xiaoyou on 16-12-12.
 */
public class DoubleArrayTrie {
    private int[] base;
    private int[] check;
    private boolean[] used;
    private int nextCheckPos;
    private static final int INIT_SIZE = 1 << 18;

    public boolean contains(String target) {
        return contains(target, 0, target.length());
    }

    public boolean contains(String target, int start, int length) {
        int parent = base[0];
        for (int i = start; i < start + length; i++) {
            if (parent + target.charAt(i) > check.length) {
                return false;
            }
            if (check[parent + target.charAt(i)] == parent) {
                parent = base[parent + target.charAt(i)];
            } else {
                return false;
            }
        }

        return base[parent] < 0;
    }

    public void clear() {
        base = null;
        check = null;
        used = null;
        nextCheckPos = 0;
    }

    public void build(List<String> keys) {
        Collections.sort(keys);
        init();
        addAll(keys);
    }

    private void init() {
        clear();
        base = new int[INIT_SIZE];
        check = new int[INIT_SIZE];
        used = new boolean[INIT_SIZE];
        nextCheckPos = 0;

        base[0] = 1;
    }

    private void addAll(List<String> keys) {
        Node parent = new Node();
        parent.depth = 0;
        parent.code = 0;
        parent.left = 0;
        parent.right = keys.size();

        List<Node> siblings = eldestChildren(parent, keys);
        doubleArrayTrie(siblings, keys);
    }

    private void resize() {
        int newSize = tableSizeFor(base.length + 1);
        base = Arrays.copyOf(base, newSize);
        check = Arrays.copyOf(check, newSize);
        used = Arrays.copyOf(used, newSize);
    }

    private int doubleArrayTrie(List<Node> siblings, List<String> keys) {
        int begin = 0;
        /*
         * 选择check基准点
         * nextCheckPos 可能比第一个sibling.code小，所以选择一个比较大的（因为儿子节点一定要在父节点之后）
         */
        int index = (siblings.get(0).code > nextCheckPos) ? siblings.get(0).code : nextCheckPos;
//        nextCheckPos = index + 1; //儿子节点的check起点，儿子的起点在父节点之后，所以+1
        boolean isFirst = true;
        outer : while (true) {
            index ++;

            if (index >= base.length) {
                resize();
            }
            if (check[index] != 0) {
                continue;
            } else if (isFirst) {
                nextCheckPos = index;
                isFirst = false;
            }


            begin = index - siblings.get(0).code;

            if (used[begin]) {
                continue;
            }

            if (begin + siblings.get(siblings.size() - 1).code >= base.length) {
                resize();
            }

            for (int i = 0; i < siblings.size(); i++) {
                if (check[begin + siblings.get(i).code] != 0) {
                    continue outer;
                }
            }
            break;
        }

        used[begin] = true;

        for (int i = 0; i < siblings.size(); i++) {
            check[begin + siblings.get(i).code] = begin;
        }

        for (int i = 0; i < siblings.size(); i++) {
            List<Node> eldestChildren = eldestChildren(siblings.get(i), keys);
            if (eldestChildren.isEmpty()) {
                base[begin + siblings.get(i).code] = -1;
            } else {
                int childBegin = doubleArrayTrie(eldestChildren, keys);
                base[begin + siblings.get(i).code] = childBegin;
            }
        }
        return begin;
    }

    private List<Node> eldestChildren(Node parent, List<String> keys) {
        int index = parent.depth;
        int prev = -1;
        List<Node> results = new ArrayList<>();

        for (int i = parent.left; i < parent.right; i ++) {
            String target = keys.get(i);
            if (target.length() < index) {
                continue;
            }

            int current = 0;
            if (target.length() > index) {
                current = target.charAt(index);
            }

            if (current != prev) {
                Node child = new Node();
                child.depth = index + 1;
                child.code = current;
                child.left = i;
                if (!results.isEmpty())
                    results.get(results.size() - 1).right = i;
                results.add(child);
            }

            prev = current;
        }

        if (!results.isEmpty()) {
            results.get(results.size() - 1).right = parent.right;
        }

        return results;
    }

    private int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= (1 << 30)) ? (1 << 30) : n + 1;
    }

    private static class Node {
        private int code;
        private int depth;
        private int left;
        private int right;

        @Override
        public String toString() {
            return "Node{" +
                    "code=" + code + "["+ (char)code + "]" +
                    ", depth=" + depth +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

}
